package com.hy.study.practice.recursion;

/**
 * 8皇后问题 使用 二维数组
 * 没有走过就是0  皇后占 了就 2
 */
public class Queue8ByDoubleArray {
    private static int max=8;
    private static int[][] map=new int[max][max];
    private static  int count=0;

    public static void main(String[] args) {
        check(0);
        System.out.println("==================="+count);
    }

    /**
     * 开始走八皇后
     * @return
     */
    private static void check(int n){
        if(n>=max){//找到了，并且部署棋盘完成了
           printArray();
            count++;
            return;
        }
        for (int i = 0; i < max; i++) {
                if(!duject(n,i)){
                    map[n][i]=2;
                    check(n+1);
                    map[n][i]=0;
                }
      }
    }

    /**
     * 判断 当前节点和其他节点是否冲突 (是否在一条直线上，或是否在一条斜线上)
     * @param i 行的坐标
     * @param j 列的坐标
     * @return
     */
    private static boolean duject(int i,int j){
        //竖线上冲突了
        for (int k = i; k >=0; k--) {
            if(map[k][j]==2){
                return true ;
            }
        }
        //横线上冲突了
        for (int k = 0; k >=j; k--) {
            if(map[i][k]==2){
                return true ;
            }
        }
        //左斜线上是否冲突
      //两数的绝对值相见相等就在一条直线上
        int row_index=i-1;
        int clo_index=j-1;
         while (row_index>=0 && clo_index>=0 ){
             if(map[row_index][clo_index]==2 &&  Math.abs(i-row_index)==Math.abs(j-clo_index)){
                 return true;
             }
             row_index--;
             clo_index--;
         }
         row_index=i-1;
         clo_index=j+1;
        while (row_index>=0 && clo_index<max ){
            if(map[row_index][clo_index]==2 &&   Math.abs(i-row_index)==Math.abs(j-clo_index)){
                return true;
            }
            row_index--;
            clo_index++;
        }
        return false;
    }


    private static  void printArray(){
        System.out.println("---------------start----------------");
        for (int i = 0; i < max; i++) {
            for (int j = 0; j < max; j++) {
                System.out.printf("%d\t",map[i][j]);
            }
            System.out.println();
        }
        System.out.println("---------------end----------------");
    }

    /**
     * 初始化棋盘
     */
    private static  void init(){
        for (int i = 0; i < max; i++) {
            for (int j = 0; j < max; j++) {
                map[i][j]=0;
            }
        }
    }
    /**
     * 求绝对值
     */
    public static int  abs(int a,int b){
    if(a<b){
        return b-a;
    }
     return a-b;
    }

    static boolean check2(int m, int n) {
        //纵轴
        for (int i = 0; i < m; i++) {
            if (map[i][n] == 1)
                return false;
        }
        //横轴
        for (int i = 0; i < n; i++) {
            if (map[m][i] == 1)
                return false;
        }
        //
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1 && Math.abs(m - i) == Math.abs(n - j))
                    return false;
            }
        for (int i = 0; i < m; i++)
            for (int j = max - 1; j > n; j--) {
                if (map[i][j] == 1 && Math.abs(m - i) == Math.abs(n - j))
                    return false;
            }

        return true;
    }
}
